#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
using namespace std;



int partation(int arr[],int begin,int end)
{
	int i = begin;
	int j = end;
	int val = arr[i];
	while (i < j)
	{
		while (i<j && arr[j]>val)
			j--;
		if (i < j)
			arr[i] = arr[j];
		i++;
		while (i < j && arr[i] < val)
			i++;
		if (i < j)
			arr[j] = arr[i];
		j--;
	}
	arr[i] = val;
	return i;



}






void SelectTopk(int arr[], int begin, int end, int k)
{
	int pos = partation(arr,begin,end);
	if (pos == k - 1)
	{
		return;
	}
	else if (pos > k - 1)
	{
		SelectTopk(arr, begin, pos-1, k);
	}
	else
	{
		SelectTopk(arr, pos + 1, end, k);
	}
}











int main()
{
	int arr[] = { 34,9,56,12,23,15,67,89,78,101 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int k = 3;
	SelectTopk(arr, 0, size - 1, k);
	for (int i = 0; i < k; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;


	return 0;
}